package 力扣._3186_施咒的最大总伤害;

import java.util.*;

class Solution {
    public long maximumTotalDamage(int[] power) {
        // 计数、排序
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int p : power) {
            cnt.put(p, cnt.getOrDefault(p, 0) + 1);
        }
        int n = cnt.size();
        int[] a = new int[n];
        int k = 0;
        for (int x : cnt.keySet()) {
            a[k++] = x;
        }
        Arrays.sort(a);
        
        long[] f = new  long[n+1];
        int j=0;
        for(int i=0;i<n;i++){
            int x = a[i];
            while(a[j]<x-2) j++; // 找到选择x时，前面可以选择的最大值
            f[i+1] = Math.max(f[i], f[j]+(long) x*cnt.get(x));
        }
        return f[n];
    }
        
}